#include <stdio.h>
#include <math.h>

#define n 6

typedef struct point {
	int a;
	int b;
}p;

typedef struct pair {
	p p1;
	p p2;
}pp;

void copy_pt(p *p1, p *p2)
{
	p1->a = p2->a;
	p1->b = p2->b;
}

void print_points(p pts[], int from, int to)
{
	int i;
	for(i=from ; i<to ; i++)
		printf("{%3d, %3d}, ", pts[i].a, pts[i].b);
	printf("\n");
	
	return;
}

void copy_points(p dest[], p src[], int from, int to)
{
	int i, j;
	
	for (i=from, j=0 ; i<to ; i++, j++) {
		//copy_pt(&dest[j], &src[i]);
		dest[j].a = src[i].a;
		dest[j].b = src[i].b;
	}

	return;
}

void sort_points_merge(p pts[], int first, int last, int sorta)
{
	int mid = (first+last)/2;
	int ai = first;
	int bi = mid+1;
	p final[last-first+1];
	int finali=0, i;

	while (ai <= mid && bi <= last) {
		if ((sorta  && pts[ai].a <= pts[bi].a) || 
			(!sorta && pts[ai].b <= pts[bi].b)) {
			copy_pt(&final[finali], &pts[ai]);
			finali++; ai++;
		} else {
			copy_pt(&final[finali], &pts[bi]);
			finali++; bi++;
		}
	}

	while (ai <= mid) {
		copy_pt(&final[finali], &pts[ai]);
		finali++; ai++;
	}
		
	while (bi <= last) {
		copy_pt(&final[finali], &pts[bi]);
		finali++; bi++;
	}

	for (i=0 ; i<last-first+1 ; i++)
		copy_pt(&pts[i+first], &final[i]);

	return;
}

void sort_points(p pts[], int a, int b, int sorta)
{
	int x, y, z, mid;
	if (a >= b) return;

	mid = (a+b)/2;
	
	sort_points(pts, a, mid, sorta);
	sort_points(pts, mid+1, b, sorta);
	sort_points_merge(pts, a, b, sorta);

	return;
}

double distance(p p1, p p2)
{
	return sqrt(pow((p2.a-p1.a), 2) + pow((p2.b-p2.b), 2));
}

double minimum_distance(pp cp1, pp cp2)
{
	double d1, d2;
	d1 = distance(cp1.p1, cp1.p2);
	d2 = distance(cp2.p1, cp2.p2);
	printf("d1 = %f : d2 = %f \n", d1, d2);
	return d1 > d2 ? d1 : d2;
}

pp ClosestSplitPair(p px[], p py[], int px_size, int py_size, int sd) 
{

}

pp ClosestPair(p px[], p py[], int px_size, int py_size)
{
	/* px_lsize = size of the left half of x array sorted by x coordinates*/
	/* px_rsize = size of the left half of x array sorted by y coordinates*/
	int px_lsize=px_size/2, px_rsize = (px_size>>1 == 1 ? (px_size+1/2) : px_size/2);

	/* py_lsize = size of the left half of y array sorted by x coordinates*/
	/* py_rsize = size of the left half of y array sorted by y coordinates*/
	int py_lsize=py_size/2, py_rsize = (py_size>>1 == 1 ? (py_size+1/2) : py_size/2);

	/* px_l = left half of the elements sorted by x coordinates */
	/* px_r = right half of the elements sorted by x coordinates */
	/* py_l = left half of the elements sorted by y coordinates */
	/* py_r = right half of the elements sorted by y coordinates */
	p px_l[px_lsize], px_r[px_rsize], py_l[py_lsize], py_r[py_rsize];

	/* The following are the closest pair */
	pp cp1, cp2, cp3;
	
	/* sd = shortest distance */
	int sd;

	/* TODO: base case */

	copy_points(px_l, px, 0, px_lsize);
	copy_points(px_r, px, px_lsize, px_rsize);
	copy_points(py_l, py, 0, py_lsize);
	copy_points(py_r, py, py_lsize, py_rsize);

	printf("px_left  : "); print_points(px_l, 0, px_lsize);
	printf("px_right : "); print_points(px_r, 0, px_rsize);
	printf("py_left  : "); print_points(py_l, 0, py_lsize);
	printf("py_right : "); print_points(py_r, 0, py_rsize);

	cp1 = ClosestPair(px_l, px_r, px_lsize, px_rsize);
	cp2 = ClosestPair(py_l, py_r, py_lsize, py_rsize);
	sd = minimum_distance(cp1, cp2);
	cp3 = ClosestSplitPair(px, py, px_size, py_size, sd);
	//sd = get_shortest(cp1, cp2, cp3);
	
	return cp1; 
}

int main(void)
{
	p pts[n] = {{1, 3}, {-2, 5}, {4, 2}, {-5, 1}, {3, -4}, {-1, 2}};
	//p pts[n] = {{1, 5}, {2, 5}, {4, 3}, {5, 1}, {3, 6}, {6, 2}};
	/* px = elements sorted by x coordinates */
	/* py = elements sorted by y coordinates */
	p px[n], py[n];
	
	/* cp = closest pair */
	pp cp;

	copy_points(px, pts, 0, n);
	copy_points(py, pts, 0, n);	

	/*
	print_points(pts);
	print_points(px);
	print_points(py);
	*/
	
	sort_points(px, 0, n-1, 1);
	sort_points(py, 0, n-1, 0);

	printf("sort x : "); print_points(px, 0, n);
	printf("sort y : "); print_points(py, 0, n);

	printf("distance : %f \n", distance(px[0], px[1]));
	

	//cp = ClosestPair(px, py, n, n);
	

	return 0;
}

